/*
 * @Author: szx
 * @Date: 2021-12-09 15:23:37
 * @LastEditTime: 2021-12-09 16:10:19
 * @Description:
 * @FilePath: \leetcode\400-499\459\459.js
 */
/**
 * @param {string} s
 * @return {boolean}
 */
// var repeatedSubstringPattern = function (s) {
//     const n = s.length;
//     for (let i = 1; i * 2 <= n; ++i) {
//         if (n % i == 0) {
//             let match = true;
//             for (let j = i; j < n; ++j) {
//                 if (s[j] != s[j - i]) {
//                     match = false;
//                     break;
//                 }
//             }
//             if (match) {
//                 return true;
//             }
//         }
//     }
//     return false;
// };

// var repeatedSubstringPattern = function (s) {
//     return (s + s).indexOf(s, 1) != s.length;
// };

var repeatedSubstringPattern = function (s) {
    const next = new Array(s.length).fill(0);
    for (let i = 1, k = 0; i < s.length; i++) {
        while (k > 0 && s[k] != s[i]) {
            k = next[k - 1];
        }
        if (s[k] == s[i]) {
            k++;
        }
        next[i] = k;
    }
    // console.log(next);
    const last = next[next.length - 1];
    if (last !== 0 && s.length % (s.length - last) === 0) return true;
    return false;
};
console.log(repeatedSubstringPattern('abaababaab'));
